Partial redundancy elimination (PRE) permits partially redundant expressions to be removed from a program. This is illustrated in FIG. 1(a) (Prior Art) and FIG. 1(b) (Prior Art). FIG. 1(a) demonstrates a typical PRE problem. In a control flow graph 100, there are four occurrences of expression h(x). For simplicity, these four occurrences are assumed to compute the same value and have no other side effects. The expression h(x) at node 7 is fully redundant because at that point h(x) has already been computed previously either at node 4 or at node 5. The expression at node 9 is partially redundant because at that point h(x) may have been computed along a path from node 1 to node 8 or not computed along a path from node 1 to node 2.
A conventional method to remove redundancy is illustrated in FIG. 1(b). To eliminate the full redundancy identified at node 7, the value of the expression h(x) computed at either node 4 or node 5 is assigned to a temporary variable t. At node 7, the computation of h(x) is replaced by t. To remove the partial redundancy at node 9, an instance of expression h(x) is inserted and saved in temporary variable t. The insertion makes the expression h(x) at node 9 fully redundant, and so its computation of h(x) is replaced by a use of temporary variable t.
The problem associated with the conventional solution to partial redundancy elimination is that it changes the run-time behavior of the original code. If the computation of h(x) throws an exception or never terminates, the upward movement of h(x) may cause the underlying code to behave differently. For instance, if h(x) throws an exception A and h(x) is moved upwards before another computation that throws an exception B. The transformation will now cause the code to throw exception A instead of B. For the same reason, downward movement may also cause similar changes in run-time behavior. For this reason, the conventional solution often cannot be used in environments that demand preservation of exception behavior.